package 题目集.动态规划.最长公共子串;

/**
 * https://www.acwing.com/problem/content/2560/
 */

import org.junit.Test;

import java.util.Scanner;

public class 最长公共子序列02_从头匹配 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        t1 = sc.nextLine().toCharArray();
        t2 = sc.nextLine().toCharArray();
        System.out.println(dpFun(t1.length, t2.length));
//        System.out.println(dfs(0, 0));
    }

    static char[] t1;
    static char[] t2;

    public static int dfs(int i, int cnt) {
        if (i == t1.length || cnt == t2.length) {
            return 0;
        }
        if (t1[i] == t2[cnt]) {
            return Math.max(dfs(i + 1, cnt), dfs(i + 1, cnt + 1) + 1);   //相等的话，可以选择不要，也可以选择要
        }
        return dfs(i + 1, cnt);
    }

    public static long dpFun(int n, int m) {
        long[][] dp = new long[n][m];
        for (int i = n-1; i >= 0; i--) {
            for (int j = m-1; j >= 0; j--) {
                if (t1[i] == t2[j]) {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i + 1][j + 1] + 1);
                } else {
                    dp[i][j] = dp[i + 1][j];
                }
            }
        }
        return dp[0][0];
    }
    @Test
    public void test(){
        int z=3;
        System.out.println(3==3||1==1&&2==z);
    }

}

